// https://leetcode.cn/problems/word-ladder/description/

// 算法思路总结：
// 1. 广度优先搜索寻找单词接龙最短转换序列
// 2. 从起始单词开始，每次改变一个字符生成新单词
// 3. 检查新单词是否在字典中且未被访问过
// 4. 找到目标单词时立即返回当前路径长度
// 5. 时间复杂度：O(26×L×N)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <queue>

class Solution 
{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        unordered_set<string> vis;
        unordered_set<string> dict(wordList.begin(), wordList.end());

        if (beginWord == endWord) return 1;
        if (dict.count(endWord) == 0) return 0;

        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);

        int ret = 1;
        const string change = "abcdefghijklmnopqrstuvwxyz";
        while (!q.empty())
        {
            int sz = q.size();
            while (sz--)
            {
                auto s = q.front();
                q.pop();
                
                if (s == endWord) return ret;

                for (int i = 0 ; i < s.size() ; i++)
                {
                    string tmp = s;
                    for (int j = 0 ; j < 26 ; j++)
                    {
                        tmp[i] = change[j];
                        if (vis.count(tmp) == 0 && dict.count(tmp) > 0)
                        {
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
            ret++;
        }

        return 0;
    }
};

int main()
{
    string beginWord1 = "hit", endWord1 = "cog";
    vector<string> wordList1 = {"hot","dot","dog","lot","log","cog"};

    string beginWord2 = "hit", endWord2 = "cog";
    vector<string> wordList2 = {"hot","dot","dog","lot","log"};

    Solution sol;

    cout << sol.ladderLength(beginWord1, endWord1, wordList1) << endl;
    cout << sol.ladderLength(beginWord2, endWord2, wordList2) << endl;

    return 0;
}